Graphs Fundamentals

Definitions

A vertex is a point in space.
We can draw a segment between two vertices u and v, (not necessarily distinct). This segment is called an edge. If u and v are the same, the edge is called a loop. Two edges that both have u and v as endpoints are considered parallel. Two edges sharing only a single endpoint are called adjacent.
A graph is a collection of vertices and edges. The order of a graph is how many vertices it has. Simple graphs are graphs without loops or parallel edges. Graphs are homeomorphically irreducible when no vertex has two edges. This is because the structure of the graph is not fundamentally changed if we remove vertices with two edges.
Two vertices on a graph are considered connected if there is a sequence of adjacent edges we can traverse to get from one vertex to the other. The sequence of edges we traverse between two vertices is called a path. If there is a path between any pair of vertices on a graph, that graph is considered connected.
Cycles are paths from a vertex to itself with at least one edge traversed.
Graphs without cycles have special names. If they are connected, they are called trees. If they are not connected (disconnected), they are forests.
Finally, let us define a notion of "equality" for graphs, known as isomorphism. In a hand-wavy sense, graphs are isomorphic if their edges connect vertices in the same way. We can call graphs distinct when they are not isomorphic to each other. The process for determining isomorphisms is a bit complicated:
1. Check if the two graphs have the same amount of vertices. If they do not, they are distinct.
2. Label each vertex in one graph x₁, x₂, .... Then, try to pair each vertex x_i to a unique vertex from the other graph y_i such that if x_i and x_j have an edge, so do y_i and y_j. Similarly, if there is no edge between x_i and x_j, then there is no edge between y_i and y_j. If no such pairing exist, the graphs are distinct.
3. However, if such a pairing can be found, these graphs are isomorphic.

Good Will Hunting (Pt 1)

A pop-culture problem involving graph theory comes from Good Will Hunting where Professor Lambeau asks his students to "[d]raw all the [distinct] homeomorphically irreducible trees with [order] 10". Based on our definitions above, we should be able to find all ten.

Solution

Will Hunting's Solution

> The scene from the movie:

Though Professor Lambeau mentions the notorious difficulty of this problem, we can see after our exploration of graph theory that it is not so hard!

Adjacency Matrices

Graphs can get messy, but we can represent their information nicely in a matrix. Given a graph G with V vertices labeled from 1 to V, the adjacency matrix of the graph is a V⨯V matrix A where A_i,j is the number of edges between vertex i and vertex j. Note that an adjacency matrix is always a square symmetric matrix.
Each entry of the adjacency matrix encodes the number of one-edge paths there are between two vertices. Since the adjacency matrix is square, we can take powers of it. For any positive integer n, entries in Aⁿ represent the number of n-edge paths between two vertices. For instance, entry [Aⁿ]_i,j is the number of paths between vertex i and vertex j involving exactly n edges.

Good Will Hunting (Pt 2)

Revisiting Good Will Hunting, the professor earlier asked his class to find the adjacency matrix of the following graph.

Additionally, he wanted them to find the matrix giving the number of 3-step walks (paths involving three edges).

Adjacency matrix solution

3-step walks solution

Bridges of Königsberg

The mathmatician Euler puzzled over the Prussian city of Königsberg, wondering how one could cross each of the seven bridges (on the map below) exactly once.

Can you find a way to do so?

Solution

> Sorry, it's impossible! However, during WWII, the city was bombed, causing two of the bridges to be destroyed. Now, Königsberg has been renamed Kaliningrad. A recent map of Kaliningrad (rendered in 2023) is below.

Now another question: can you cross these remaining five bridges exactly once?

Solution

> Here's how you could cross these five bridges on your next vacation:

Special Paths

There are four particularly special types of paths.

An Eulerian path is a path that uses every edge in a graph exactly once.
Similarly, an Eulerian cycle is a cycle that uses every edge in a graph exactly once.
A path where each vertex on the graph is an endpoint to exactly two edges is called a Hamiltonian cycle.
Instead, a Hamiltonian path has two vertices as endpoints to exactly one edge while all the rest are endpoints to two.

In both Eulerian paths and cycles, all edges of a graph are included in the path. In both Hamiltonian paths and cycles, all vertices are endpoints of edges on the path.

Challenge: Finding Special Paths (Pt 1)

Try to find rules for when a graph has one of these special paths.

Hint for Eulerian

Hint for Hamiltonian

Solution for Eulerian

Solution for Hamiltonian

Directed Graphs

So far, the graphs we have talked about are undirected, meaning if an edge exists between vertex i and j, we can travel from i to j and vice-versa. However, on a directed graph, edges specify a single direction of travel. For instance, we can now have an edge pointing from i to j, indicating we can travel from i to j, but not the other way around.
Adjacency matrices for directed graphs may no longer be symmetric. Now, the i,j-th entry of an adjacency matrix is the number of edges that point from i to j specifically.

Challenge: Finding Special Paths (Pt 2)

Try to come up with a rule for when Eulerian and Hamiltonian paths/cycles exist on a directed graph. These may be similar to the rules you have come up with earlier.

Solution for Eulerian

Solution for Hamiltonian